a = [6, 1, 2, 5, 4, 3, 9, 7, 10, 8]
left=0
right=len(a)-1
right_l=0
right_r=len(a)-1
while left < right:
    print(a)
    t = a[left]
    i = left
    j = right
    while(i != j):
        while(a[j] >= t and i < j):
            j -= 1
        while(a[i] <= t and i < j):
            i += 1
        if i < j:
            a[i], a[j] =a[j],a[i]
    a[left] = a[i]
    a[i]=t
    if right-left==3:
        left=right_l
        right=right_r
        right_l=right_r+1
        right_r=(right_r+1)+right_r
    else:
        right//=2
        right_l=right+1
        right_r=right_r//2+right_l-1
    print(a[right_l:right_r])

print(a)